import datastructure.linklist.ListNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/4 10:39
 * @description:
 */
public class Solution25 {
    //1,2,3,4,5
    //2,1,4,3,5
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k <= 1) {
            return head; // 空链表或k=1无需翻转
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy; // pre指向每组翻转前的前驱节点（初始为dummy）

        while (true) {
            // 1. 检查剩余节点是否至少有k个
            ListNode check = pre.next;
            int count = 0;
            while (check != null && count < k) {
                check = check.next;
                count++;
            }
            if (count < k) {
                break; // 剩余节点不足k个，停止翻转
            }

            // 2. 翻转当前k个节点（pre.next到check前的节点）
            ListNode cur = pre.next; // 当前组的第一个节点
            ListNode next; // 记录cur的下一个节点
            for (int i = 0; i < k - 1; i++) {
                next = cur.next; // 保存下一个节点
                // 翻转：将next节点提到当前组的最前面（pre后面）
                cur.next = next.next;
                next.next = pre.next;
                pre.next = next;
            }

            // 3. 更新pre，准备处理下一组
            pre = cur; // 翻转后，当前组的最后一个节点是原第一个节点（cur）
        }

        return dummy.next;
    }

    public ListNode reverseKGroup2(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode pre = head, index = head.next;
        int m = 0;
        while (++m < k && index != null) {
            pre.next = index.next;
            index.next = head;
            head = index;
            index = pre.next;
        }
        if (m < k) {
            reverseKGroup2(head, m);
        }
        pre.next = reverseKGroup(index, k);
        return head;
    }

    public static void main(String[] args) {
        Solution25 solution = new Solution25();
        // 测试用例：1->2->3->4->5，k=2 → 预期 2->1->4->3->5
        ListNode head = ListNode.arrayToList(new int[]{1, 2, 3, 4, 5});
        ListNode newHead = solution.reverseKGroup(head, 2);
        ListNode.printList(newHead); // 输出：2 -> 1 -> 4 -> 3 -> 5

        // 测试用例：1->2->3->4->5，k=3 → 预期 3->2->1->4->5
        ListNode head2 = ListNode.arrayToList(new int[]{1, 2, 3, 4, 5});
        ListNode newHead2 = solution.reverseKGroup(head2, 3);
        ListNode.printList(newHead2); // 输出：3 -> 2 -> 1 -> 4 -> 5
    }
}
